package chp01.YusufRing;

class MyCounter {
    private int number;
    private int place;

    public MyCounter(int number) {
        this.number = number;
        this.place = 0;
    }

    public int next() {
        //只做输出，并不判断产生的下一个人是不是已经退出环
        place %= number;
        return place++;
    }

    public int getPlace(){
        return place;
    }
}

class MySieve {
    private int m;
    private boolean [] states;
    private MyCounter counter;

    public MySieve(int number, int mNum) {
        counter = new MyCounter(number);
        states = new boolean[number];
        this.m = mNum;
    }

    int next() {
        for (int i = 0; i < m; i++) {
            while(states[counter.next()]);
        }
        int x = counter.getPlace();
        states[x-1] = true;
        return x;
    }
}

public class JosephCircleOOP_State {
    public static void main(String[] args) {
        // int n = 5, M = 3;
        // int n = 100, M = 5;
        int n = 1000, M = 7;

        long startTime = System.currentTimeMillis(); //获取开始时间
        MySieve sieve = new MySieve(n, M);
        // 每次筛选一个，筛选n次，最后一次筛选出的就是最后留下来的人
        for (int i = 0; i < n; i++) {
            int out = sieve.next();
            System.out.println("Filtered out number at time (" + i + ") is " + out);
            // if (i == n-1)
            //     System.out.println("The last number left is: " + out);
        }
        long endTime = System.currentTimeMillis(); //获取结束时间

        System.out.println("Total Running Time is: " + (endTime - startTime) + "ms"); //输出程序运行时间
    }
}
